The invention relates to the field of data networks, and in particular to peer to peer overlay networks. Peer to peer networks are distributed data networks without any centralized hierarchy or organization. Peer to peer data networks provide a robust and flexible means of communicating information between large numbers of computers or other information devices, referred to in general as nodes.
An overlay network is a logical or virtual network organization that is imposed on nodes connected by one or more types of underlying physical network connections. In an overlay network, nodes are connected by virtual or logical links, each of which can correspond with one or more paths in an underlying physical network. Overlay networks are typically implemented in hardware and/or software operating in the application layer or other top-level layer of an OSI network stack or other type of networking protocol.
One class of peer to peer overlay networks is referred to as distributed hash table overly networks. Distributed hash table overlay networks use a hash function to generate and assign one or more key values to a unique node. The set of all possible key values is referred to as a hash space. Nodes are organized in the hash space according to their assigned key values. The hash function is selected so that nodes are approximately evenly distributed throughout the hash space. Distributed hash table overlay networks are typically highly scalable, often supporting millions of nodes; robust, allowing nodes to join or leave frequently; and efficient, routing a message to a single destination node quickly.
There are numerous different types of distributed hash table overlay networks. One type of peer to peer overlay network is a chord network. The chord overlay network protocol is described in detail in “Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”, Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan, IEEE/ACM Transactions on Networking, Vol. 11, No. 1, pp. 17-32, February 2003.
Distributed hash table overlay networks such as Chord create finger tables for each node that specify neighboring nodes in the overlay network. Neighboring nodes typically have a hash or key value offset from the current node by a predetermined amount. Distributed hash table overlay networks such as Chord route data traffic by forwarding information through a sequence of one or more neighboring nodes until the data traffic reaches its intended destination.
Typical distributed hash table overlay networks create finger tables for each node by determining a desired destination key value for each finger table entry. The overlay network then selects the node with a key value closest to the desired destination key value as the neighboring node. For example, if a first node with a key value of 17 needs a neighboring node with a key value of approximately 33, the overlay network may select a second node with a key value 31 as the neighboring node.
In other distributed hash table overlay networks, flexible neighbor selection allows the overlay network to select any node within a specific range of the desired destination key value as the neighboring node. For example, if a first node with a key value of 17 needs a neighboring node with a key value of approximately 33, the overlay network may select a second node with a key value 31 or a third node with a key value of 27 as the neighboring node. Neighboring nodes can be selected using different criteria, such as round trip time, node capabilities, node bandwidth, network quality of service, and security.
It thus is desirable for an overlay network to select neighboring nodes using a criteria that is indicative of the nodes networking capabilities so as to optimize the overall performance of the overlay network.